package com.moyoutian.leetcode;

import java.util.*;

/**
 * 524. 通过删除字母匹配到字典里最长单词
 * <p>
 * 给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
 * <p>
 * 如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
 * 输出："apple"
 * <p>
 * 示例 2：
 * <p>
 * 输入：s = "abpcplea", dictionary = ["a","b","c"]
 * 输出："a"
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 1000
 * 1 <= dictionary.length <= 1000
 * 1 <= dictionary[i].length <= 1000
 * s 和 dictionary[i] 仅由小写英文字母组成
 */
public class Demo524 {

    public static void main(String[] args) {
        String s = "abce";
        String[] dictionary = {"abe", "abc"};
        List<String> list = new ArrayList<>(Arrays.asList(dictionary));
        System.out.println(findLongestWord(s, list));
    }


    public static String findLongestWord(String s, List<String> dictionary) {
        Collections.sort(dictionary);
        int maxIndex = -1;
        int maxLen = 0;
        for (int i = 0; i < dictionary.size(); i++) {
            //如果当前的字符串长度大于最大记录字符串长度，在开始比较。如果包含在交换
            if (dictionary.get(i).length() > maxLen && findWord(s, dictionary.get(i))) {
                maxIndex = i;
                maxLen = dictionary.get(i).length();
            }
        }
        return maxIndex == -1 ? "" : dictionary.get(maxIndex);
    }

    /**
     * 查看当前字符是否包含
     *
     * @param s    字符
     * @param word 被包含字符
     */
    public static boolean findWord(String s, String word) {
        if (s == null || s.length() < word.length()) {
            return false;
        }
        int wordIndex = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == word.charAt(wordIndex)) {
                wordIndex++;
                if (wordIndex == word.length()) {
                    return true;
                }
            }

        }
        return false;
    }
}
